package github.labuladong;

import java.util.Arrays;
import java.util.Collections;

/**
 * @Author: DRevelation
 * @Date: 2020/12/14 15:55
 * 给你 k 种⾯值的硬币，⾯值分别为  c1, c2 ... ck  ，每种硬
 * 币的数量⽆限，再给⼀个总⾦额  amount  ，问你最少需要⼏枚硬币凑出这个
 * ⾦额，如果不可能凑出，算法返回 -1
 */
public class CoinChange {

    private static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = amount + 1;
        }
        for (int i = 0; i < dp.length; i++) {
            for (int coin : coins) {
                //子问题无解，跳过
                if (i - coin < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }


    public static void main(String[] args) {
        int[] coin = new int[]{1, 2, 5};
        System.out.println("coinChange(coin, 14) = " + coinChange(coin, 14));
    }
}
